package LimitedTimeGame.Day_0326.night;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zxc
 * @date 2023/03/26 20:06
 **/
public class List {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public  ListNode reorderList (ListNode head) {
        ListNode dummy = new ListNode();
        Queue<ListNode> queue = new LinkedList<>();
        int len = 1;
        ListNode start = head;
        ListNode now = head;
        ListNode next = head.next;
        while(now != null){
            // 当len == 2时，则选择将当前子链表加入到queue;
            if(len == 2){
                now.next = null;
                now = next;
                next = next.next;
                queue.add(start);
                System.out.println(start.val);
                start = now;
                len = 1;
            }
            else {
                // 链表节点后移
                len++;
                now = now.next;
                next = next.next;
                // 若是最后有且仅剩下一个链表节点的话，则选择将其直接加入到队列中;
                if(now == null){
                    queue.add(start);
                    break;
                }
            }
        }
        ListNode node = dummy;
        while(!queue.isEmpty()){
            ListNode p1 = queue.poll();
            if(queue.isEmpty()){
                node.next = p1;
                break;
            }
            ListNode p2 = queue.poll();

            node.next = p2;
            // 即，保证node链表节点永远为 新构建链表的尾节点;
            while(node.next != null){
                node = node.next;
            }

            node.next = p1;
            while(node.next!= null){
                node = node.next;
            }
        }
        return dummy.next;
    }
    class ListNode {
        int val;
        ListNode next = null;
    }
}
